/* 同余
* 1.拓展欧几里得算法
    (a,b) = d;
    ax0 + by0 = d

    x = x0 + k(a/d)
    y = y0 - k(b/d)

    ax = 1(mod b)

    ax = (b, a mod b)

*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

int exgcd(int a, int b, int &x, int &y) //ax+by = gcd(a,b) x,y是整数
{
    if(!b) //此时 gcd(a,0) = a -> ax+by=gcd(a,b) -> x=0,y=1
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a%b, y, x); //gcd(b, a % b) bx' + (a % b)y' = gcd(b, a % b) 
     y -= a / b * x; // x = y'，y = x' - (a / b) * y'
    return d;
}

int main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    int a, b; cin >> a >> b;

    int x, y;
    exgcd(a, b, x, y);

    cout << (x % b + b) % b << endl; //x%b的最小非负余数

}